from collections import deque
from pythonds import BinaryTree


def preorderTraversal( root) :
    # 保存结果
    result = []

    def traversal(root):
        if root == None:
            return
        result.append(root.key)  # 前序
        traversal(root.getLeftChild())  # 左
        traversal(root.getRightChild())  # 右

    traversal(root)
    return result


def levelOrder(root) :
    results = []
    if not root:
        return results


    que = deque([root])

    while que:
        size = len(que)
        result = []
        for _ in range(size):
            cur = que.popleft()
            result.append(cur.key)
            if cur.getLeftChild():
                que.append(cur.getLeftChild())
            if cur.getRightChild():
                que.append(cur.getRightChild())
        results.append(result)

    return results
root=BinaryTree('A')
root.insertLeft('B')
root_left=root.getLeftChild()
root_left.insertLeft("D")
root_left.insertRight("E")
root_left_right=root_left.getRightChild()
root_left_right.insertRight("J")
root.insertRight("C")
root_right=root.getRightChild()
root_right.insertLeft("F")
root_right_left=root_right.getLeftChild()
root_right_left.insertRight("I")
root_right.insertRight("G")
p=preorderTraversal(root)
print(p)
l=levelOrder(root)
print(l)
